home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / devel / db / esm-3.1 / esm-3 / usr / local / sm / src / client / version / findAdjacent.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-05-05  |  4.6 KB  |  174 lines
  1. /*
  2.  *   $RCSfile: findAdjacent.c,v $  
  3.  *   $Revision: 1.1.1.1 $  
  4.  *   $Date: 1996/05/04 21:55:32 $      
  5.  */ 
  6. /**********************************************************************
  7. * EXODUS Database Toolkit Software
  8. * Copyright (c) 1991 Computer Sciences Department, University of
  9. *                    Wisconsin -- Madison
  10. * All Rights Reserved.
  11. *
  12. * Permission to use, copy, modify and distribute this software and its
  13. * documentation is hereby granted, provided that both the copyright
  14. * notice and this permission notice appear in all copies of the
  15. * software, derivative works or modified versions, and any portions
  16. * thereof, and that both notices appear in supporting documentation.
  17. *
  18. * THE COMPUTER SCIENCES DEPARTMENT OF THE UNIVERSITY OF WISCONSIN --
  19. * MADISON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" CONDITION.  
  20. * THE DEPARTMENT DISCLAIMS ANY LIABILITY OF ANY KIND FOR ANY DAMAGES
  21. * WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  22. *
  23. * The EXODUS Project Group requests users of this software to return 
  24. * any improvements or extensions that they make to:
  25. *
  26. *   EXODUS Project Group 
  27. *     c/o David J. DeWitt and Michael J. Carey
  28. *   Computer Sciences Department
  29. *   University of Wisconsin -- Madison
  30. *   Madison, WI 53706
  31. *
  32. *     or exodus@cs.wisc.edu
  33. *
  34. * In addition, the EXODUS Project Group requests that users grant the 
  35. * Computer Sciences Department rights to redistribute these changes.
  36. **********************************************************************/
  37.  
  38. #include <stdio.h>
  39. #include "ess.h"
  40. #include "checking.h"
  41. #include "list.h"
  42. #include "io.h"
  43. #include "tid.h"
  44. #include "object.h"
  45. #include "bf.h"
  46. #include "chunk.h"
  47. #include "lgobject.h"
  48. #include "pool.h"
  49. #include "trace.h"
  50. #include "error.h"
  51. #include "version_graph.h"
  52. #include "version_funcs.h"
  53. #include "lg_extfuncs.h"
  54. #include "sm_macro.h"
  55.  
  56. /*
  57.  * FindAdjacent returns a list of the root nodes of all versions 
  58.  * adjacent to a version.  Adjacent means all direct children and
  59.  * the parent of the version.  This definition also extends 
  60.  * recursively to tombstoned versions.  For example a tombstone
  61.  * child actually represents all the direct children of the tombstone.
  62.  * Also, a tombstone parent represents all the direct children of 
  63.  * all tombstone ancestors up to a non-tombstone ancestor.
  64.  */
  65.  
  66.  
  67.  int
  68. findAdjacent(
  69.     BUFGROUP        *bufGroup,
  70.     VERSIONGRAPH     *graph,        /* graph containing node        */
  71.     VHGNODEID        nodeId,     /* node to mark pending            */
  72.     LIST            *adjList,    /* list of adjacent versions    */
  73.     POOL            *adjListPool /* pool for adj list nodes     */
  74. )
  75. {
  76.     VHGNODE*     node;
  77.     VHGNODEID    parentId;
  78.     VHGNODEID    childId;
  79.     LGNODELIST    *adjVersion;
  80.     BOOL        found;
  81.  
  82.     TRPRINT(TR_VERSION, TR_LEVEL_1, ("finding adjacent to node %d \n", nodeId) );
  83.  
  84.     CHECK_VERSIONGRAPH_MAGIC(graph);
  85.     
  86.     /*
  87.      *  Validate  nodeId
  88.      */
  89.     if (nodeId >= graph->nodeCount) {
  90.         SM_ERROR(TYPE_WARNING, esmINTERNAL);
  91.         return esmFAILURE;
  92.     }
  93.  
  94.     /*
  95.      *  Get a pointer to the node
  96.      */
  97.     node = &graph->nodeArray[nodeId];
  98.  
  99.     /*
  100.      *  Do some defensive error checking.  The node should be frozen
  101.      */
  102.     CHECK_VHGNODE_MAGIC(node);
  103.     SM_ASSERT(LEVEL_3, (node->flags & V_frozen));
  104.  
  105.     /*
  106.      *    The first half of the search is to determine the "parents" of 
  107.      *    the version.  This involves searching up the VHG searching
  108.      *    for the first non-tombstone parent.  For each tombstone parent
  109.      *    found, all its direct parents are considered "parents" of 
  110.      *    the version.
  111.      */
  112.     parentId = node->parentId;
  113.     childId  = nodeId;
  114.     found = FALSE;
  115.     while (parentId != VHGNULLNODE  && !found) {
  116.  
  117.         /*
  118.          *    See if the parent is a tombstone
  119.          */
  120.         if (graph->nodeArray[parentId].flags & V_tombstone) {
  121.  
  122.             /*
  123.              *    Add the children of the parent to the list
  124.              */
  125.             findDirectChildren(bufGroup, graph, parentId, childId, 
  126.                                 adjList, adjListPool);
  127.             
  128.             /*
  129.              *    advance up to the next parent
  130.              */
  131.             childId = parentId;
  132.             parentId = graph->nodeArray[parentId].parentId;
  133.  
  134.         } else {
  135.             
  136.             /*
  137.              *    A non-tombstone parent was found, so add it
  138.              *    to the list 
  139.              */
  140.  
  141.             /*
  142.               *    First get a list element and initialize it
  143.              */
  144.             if ((adjVersion = (LGNODELIST *) poolDeq( adjListPool )) == NULL) {
  145.                 /*
  146.                  *  set the error code and return
  147.                  */
  148.                 SM_ERROR(TYPE_WARNING, esmNOFREELGNODELIST);
  149.                 return(esmFAILURE);
  150.             }
  151.             if (lg_GetRootNodePid(bufGroup, 
  152.                                   &graph->nodeArray[parentId].oid, 
  153.                                   &adjVersion->pid, &adjVersion->slot) ) {
  154.                 return(esmFAILURE);
  155.             }
  156.             
  157.             /*
  158.              *    Add it to the list, and stop the search
  159.              */
  160.             listEnq(adjList, &adjVersion->list);
  161.             found = TRUE;
  162.         }
  163.     }
  164.  
  165.     /*
  166.      *    The second half of the search is to find the direct children
  167.      *    of the version.
  168.      */
  169.     findDirectChildren(bufGroup, graph, nodeId, VHGNULLNODE, adjList,
  170.                         adjListPool);
  171.  
  172.     return(esmNOERROR);
  173. }
  174.